Lemme de Sauer-Shelah

Lemme de Sauer-Shelah :

$\mathcal S$ est une classe de Fonction de décision formées de fonctions indicatrices
la Dimension de Vapnik-Chervonenkis est finie : $\operatorname{dim}_\text{VC}(\mathcal S)=:h\lt +\infty$
$l\geqslant h$

$$\Huge\iff$$

on a une borne du Coefficient de pulvérisation : $$N_\mathcal S(l)\leqslant\sum^h_{i=0}\binom li$$

START
Ω Basique (+inversé optionnel)
Recto: Donner une particularité fondamentale des familles de Dimension de Vapnik-Chervonenkis finie.
Verso: Leur Fonction de croissance augmente au plus polynomialement en fonction de $l$.
Bonus:
Carte inversée ?:
END

Math'φsics

Formulaire de report